/*
 * Dynamic allocating array data structure.
 * Copyright (C) 2006 Bob Zimmermann <rpz@cse.wustl.edu>
 *
 *  This file is a part of BAT.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * darray.c
 *
 * This is a dynamic array data structure which is designed to make your life
 * slightly easier when handling memory allocation of sets that do not have
 * deterministic size in your program.
 *
 */

#include<stdlib.h>
#include<stdio.h>
#include<string.h>

#include "darray.h"

static void _darray_bail();

darray_ops_t darray_ops_ops = {
  (darray_copy_op) darray_copy,
  NULL,
  NULL,
  (darray_delete_op) darray_delete
};

/*
 * darray_ops_new
 *
 * Create a new darray ops function set.  You may pass NULL to any of these
 * parameters if you don't wish to have a callback.
 */
darray_ops_t *
darray_ops_new(darray_copy_op copy, darray_order_op order,
	       darray_identify_op identify, darray_delete_op delete)
{
  darray_ops_t *dao;
  dao = malloc(sizeof(darray_ops_t));
  if (dao == NULL)
    _darray_bail();

  dao->copy = copy;
  dao->order = order;
  dao->identify = identify;
  dao->delete = delete;

  return dao;
}

darray_ops_t *
darray_ops_copy(const darray_ops_t * dao)
{
  darray_ops_t *copy;
  copy = malloc(sizeof(darray_ops_t));

  copy->copy = dao->copy;
  copy->order = dao->order;
  copy->identify = dao->identify;
  copy->delete = dao->delete;

  return copy;
}

void
darray_ops_delete(darray_ops_t * dao, int befrei)
{
  if (befrei)
    free(dao);
}


/*
 * darray_new
 *
 * Create a new darray container.  You can pass a guessed minimum size for the
 * container in number of elements.
 */
darray_t *
darray_new(da_pos_t init_size, darray_ops_t * ops)
{
  darray_t *da;

  da = malloc(sizeof(darray_t));

  if (ops == NULL)
    da->ops = darray_ops_new(NULL, NULL, NULL, NULL);
  else
    da->ops = ops;

  da->n_elts = init_size;
  da->pos = 0;

  /* Expansion will not work with a size of less than 1 */
  if (da->n_elts < 2)
    da->n_elts = 2;

  da->data = malloc(da->n_elts * sizeof(void *));

  if (da->data == NULL)
    _darray_bail();

  return da;
}

/*
 * darray_copy
 *
 * Copy the contents of a container to another.  The elements themselves are
 * copied only if there is a copy function defined in the ops.
 */
darray_t *
darray_copy(const darray_t * da)
{
  darray_t *copy;
  int i;

  copy = darray_new(da->n_elts, darray_ops_copy(da->ops));

  if (da->ops->copy == NULL) {
    memcpy(copy->data, da->data, da->n_elts * sizeof(void *));
    copy->pos = da->pos;
  }
  else
    for (i = 0; i < da->pos; i++)
      darray_add(copy, da->ops->copy(darray_peek(da, i)));

  return copy;
}

/*
 * darray_delete
 *
 * Free the memory associated with the darray.  This will clobber your array, so
 * don't use this if you plan to keep the data (see darray_retire).
 */
void
darray_delete(darray_t * da, int befrei)
{
  int i;

  if (da->ops != NULL && da->ops->delete != NULL)
    for (i = 0; i < da->pos; i++)
      da->ops->delete(darray_get(da, i), 1);

  if (da->ops != NULL)
    darray_ops_delete(da->ops, 1);

  da->ops = NULL;

  if (da->data != NULL)
    free(da->data);

  if (befrei)
    free(da);
}

/*
 * darray_add
 *
 * Add an element to the darray.  Note that the element is copied into the
 * internal structure, not simply placed.  So if you don't need the data
 * after you insert it into the array, free it.
 */
void
darray_add(darray_t * da, const void *data)
{
  if (da->pos == da->n_elts) {
    da->n_elts *= 2;
    da->data = realloc(da->data, da->n_elts * sizeof(void *));
    if (da->data == NULL) {
      _darray_bail();
    }
  }
  darray_set(da, da->pos, data);
  da->pos++;
}

/*
 * darray_clear
 *
 * Clear the dynamic array, but to not free the memory associated with 
 * the dynamic array.
 *
 */

void
darray_clear(darray_t *da, int befrei)
{
  int i;
  if(befrei && da->ops != NULL && da->ops->delete != NULL) {
    for(i = 0; i < da->pos; i++)
      da->ops->delete(da->data[i], 1);
  }
  da->pos = 0;
}

/*
 * darray_get, darray_peek
 *
 * Returns a pointer to the element in the array at the given index
 */
void *
darray_get(darray_t * da, da_pos_t index)
{
  /*
   * return *((void **) ((da_pos_t long) da->data + (index *
   * sizeof(void *))));
   */
  return da->data[index];
}

const void *
darray_peek(const darray_t * da, da_pos_t index)
{
  /*
   * return *((void **) ((da_pos_t long) da->data + (index *
   * sizeof(void *))));
   */
  return da->data[index];
}


/*
 * darray_remove
 *
 * Remove the element from the array.
 */
/*
 * XXX:this should probably return a copy of the item so any mem handling can
 * be done after removing from the array
 */
void *
darray_remove(darray_t * da, da_pos_t pos, int befrei)
{
  int i;
  void *old;

  old = NULL;
  if (da->ops->delete != NULL && befrei)
    da->ops->delete(da->data[pos], befrei);
  else
    old = da->data[pos];
  da->pos--;

  for (i = pos; i < da->pos; i++)
    darray_set(da, i, darray_get(da, i + 1));

  return old;
}

/*
 * darray_set
 *
 * Set an element in the array to a certain value.  The array is assumed to be
 * at least as big as the array index + 1.  Returns a pointer to the location
 * of the newly set object.
 */
void
darray_set(darray_t * da, da_pos_t index, const void *data)
{
  memcpy(&da->data[index], &data, sizeof(void *));
}

/*
 * darray_insert
 *
 * Insert an object at a specific position.  O(N)
 */
void
darray_insert(darray_t * da, da_pos_t index, const void *data)
{
  int i;
  void *last, *ptr;
  if (index == darray_size(da)) {
    darray_add(da, data);
    return;
  }
  last = darray_get(da, da->pos);
  darray_add(da, last);

  for (i = darray_size(da) - 2; i > index; i--) {
    ptr = darray_get(da, i - 1);
    darray_set(da, i, ptr);
    /* memcpy(darray_get(da, i), &ptr, sizeof(void *)); */
  }

  darray_set(da, index, data);
  /* memcpy(darray_get(da, index), &data, sizeof(void *)); */
}

/*
 * darray_pos
 *
 * Find an object's position in the dynamic array.
 */
da_pos_t
darray_pos(darray_t * da, const void *ptr)
{
  int i;

  for (i = 0; i < da->pos; i++)
    if (darray_get(da, i) == ptr)
      break;
  if (i == da->pos) {
    fprintf(stderr, "darray_pos: Object not found.\n");
    exit(1);
  }
  return i;
}

/*
 * darray_place
 *
 * Put an object into the array according to a given order.  The array is
 * assumed to be sorted.  Return the position of the newly placed object. If
 * a non-null comparison function is passed, it will be used instead of the
 * set operation.
 */
da_pos_t
darray_place(darray_t * da, const void *data, darray_order_op compar)
{
  int pos, sz;

  sz = darray_size(da);
  /* darray_get(da, pos) */
  for (pos = 0; pos < sz && compar(&data, &((const void **) da->data)[pos]) > 0;
       pos++);
  darray_insert(da, pos, data);

  return pos;
}


/*
 * darray_find
 *
 * Find and return the first object which matches the given comparison function.
 * The comparison callback will get the object as the first parameter and the
 * key as the second parameter.  Passing a non-null comparison function will
 * override the default operation.  Return NULL if none is found.
 */
void *
darray_find(darray_t * da, const void *key, darray_identify_op identify)
{
  int i, sz;
  sz = darray_size(da);
  for (i = 0; i < sz; i++) {
    if (!identify(da->data[i], key))
      return da->data[i];
  }
  /* ptr = darray_get(da, i); */

  return NULL;
}

/*
 * darray_pop Remove the final element from the darray and return a copy of
 * that element.
 */
void
darray_pop(darray_t * da)
{
  da->pos--;
}

/*
 * darray_size The size, in number of elements, that have been added to the
 * array.
 */
da_pos_t
darray_size(darray_t * da)
{
  return da->pos;
}

/*
 * darray_gc Garbage collection.  Cleans up the extra memory that is unused
 * by the darray. Good to call before reclaiming the array with
 * darray_retire.
 */
void
darray_gc(darray_t * da)
{
  da->data = realloc(da->data, da->pos * sizeof(void *));
}

/*
 * darray_sort
 *
 * Sort the elements according to a strict weak ordering defined by the function
 * compar.  The function compar is an optional pointer to a function which
 * returns <0 if first should be ordered before second, 0 if first is equal
 * to second, and >0 if first should be ordered after second. The darray_ops
 * pointer is used by default.  Passing a non-null
 */

void
darray_sort(darray_t * da, int (*order) (const void **, const void **))
{
  if (order != NULL)
    qsort(da->data, da->pos, sizeof(void *),
	  (int (*)(const void *, const void *)) order);
  else if (da->ops->order != NULL)
    qsort(da->data, da->pos, sizeof(void *),
	  (int (*)(const void *, const void *)) da->ops->order);
}

/*
 * darray_get_array Return an array of pointers to the objects stored in the
 * dynamic array.
 */
void **
darray_get_array(darray_t * da)
{
  return (void **) da->data;
}

/*
 * darray_release
 *
 * Return the contained array and free the memory used by the darray.
 * The darray object should not be used after this call; you may consider
 * it deleted.
 */
void **
darray_release(darray_t * da, da_pos_t *sz, int befrei)
{
  void **arr;

  arr = darray_get_array(da);
  *sz = darray_size(da);

  if (da->ops != NULL)
    darray_ops_delete(da->ops, 1);
  da->ops = NULL;

  if (befrei) {
    free(da->ops);
    free(da);
  }

  return arr;
}

void
_darray_bail()
{
  fprintf(stderr, "darray: Out of memory.\n");
  exit(1);
}

/*
 * int int_comp(const void *a, const void *b) { if(*((int *)a) > *((int *)b))
 * { return 1; } else if(*((int *)a) < *((int *)b)) { return -1; } else {
 * return 0; } }
 *
 * struct gobble { int i; char gggg[500000]; };
 *
 * int main(int argc, char *argv[]) { darray_t *da; int i, *ip; struct gobble g;
 *
 * da = darray_new(5, sizeof(int)); //for(j = 0; j < 500000; j++) { //for(i =
 * 5000; i >= 0; i--) { //g.i = i; //darray_add(da, &g); //} //}
 *
 * for(i = 0; i < 10; i++) darray_add(da, &i); while((ip = darray_pop(da))) {
 * printf("%d ", *ip); free(ip); }
 *
 * for(i = 0; i < 10; i++) darray_add(da, &i);
 *
 * //darray_sort(da, int_comp); //darray_gc(da);
 *
 * for(i = 0; i < darray_size(da); i++) { printf("%d ", *((int *)darray_get(da,
 * i))); } printf("\n");
 *
 * return 0; }
 */
